As the number of components in VLSI circuitry has grown, the testing of such circuitry has become complex. The testing is complicated because it is impractical to probe internal nodes of the circuit. As a consequence, the usual manner of testing such circuits is to apply a set of input vectors to the input terminals of the circuit and for each input vector to observe the resulting output vector at the output terminals to ascertain whether the output vector observed corresponds to the output vector expected for the particular applied input vector. Each input vector typically is chosen to test for a particular one of the faults thought possibly to be found in the circuit. For complex circuits the number of possible faults tends to be large so that a large set of test vectors is needed. An important factor in this process is having a set of input vectors for use in the testing that will provide the maximum amount of relevant information in the shortest time of testing. Generally, the testing is done automatically by equipment designed to provide a prescribed set of input vectors sequentially to a sample circuit being tested to check the output vectors observed for conformance with the output vectors expected and to reject nonconforming samples..
Typically, choosing a set of test vectors is part of the design process of the integrated circuit. Normally, even before a phototype chip of a desired integrated circuit is built, there is developed an appropriate set of vectors for use in testing the eventual chip. This process involves establishing various faults that possibly might arise in the circuit and developing a set of vectors for testing for all or most of such possible faults.
Various techniques are in use for developing such sets of test vectors but there remains room for improvement. Typically previous techniques do not guarantee the identification of all logical consequences of a partial set of signal assignments. It is desirable to identify all such consequences so that a branch and bound method can effectively avoid signal assignments that will not lead to a test vector. Also previous techniques generally do not establish the complexity of determining the logical consequences, and it remains unclear if it is at all possible to determine all the consequences using reasonable amount of resources. Finally, these techniques tend not to be easily parallelizable.